# Powered by Python 2.7

# To cancel the modifications performed by the script
# on the current graph, click on the undo button.

# Some useful keyboards shortcuts : 
#   * Ctrl + D : comment selected lines.
#   * Ctrl + Shift + D  : uncomment selected lines.
#   * Ctrl + Space  : run script.
#   * Ctrl + F  : find selected text.
#   * Ctrl + R  : replace selected text.

from tulip import *

# the updateVisualization(centerViews = True) function can be called
# during script execution to update the opened views

# the pauseScript() function can also be called to pause the script execution.
# To resume the script execution, you will have to click on the "Run script " button.

# the main(graph) function must be defined 
# to run the script on the current graph
def makeTreeA(graph,viewColor, viewLabel):
	
	tree1 = tlp.newSubGraph(graph, "firstTree");
	Nroot = tree1.addNode();
	#viewColor.setNodeValue(Nroot, tlp.Color(0,0,255));
	#viewLabel.setNodeValue(Nroot, "b");
	N1 = tree1.addNode();
	N2 = tree1.addNode();
	N3 = tree1.addNode();
	N4 = tree1.addNode();
	N5 = tree1.addNode();
	N21 = tree1.addNode();
	N31 = tree1.addNode();
	
	tree1.addEdge(Nroot, N1);
	tree1.addEdge(Nroot, N2);
	tree1.addEdge(Nroot, N3);
	tree1.addEdge(Nroot, N4);
	tree1.addEdge(Nroot, N5);
	tree1.addEdge(N2, N21);
	tree1.addEdge(N3, N31);
	
	return tree1;
def makeTreeB(graph, viewColor, viewLabel):
	
	tree2 = tlp.newSubGraph(graph, "secondTree");
	Nroot = tree2.addNode();
	#viewColor.setNodeValue(Nroot, tlp.Color(0,0,255));
	#viewLabel.setNodeValue(Nroot, "b");
	N1 = tree2.addNode();
	N2 = tree2.addNode();
	N3 = tree2.addNode();
	
	N21 = tree2.addNode();
	N31 = tree2.addNode();
	N32 = tree2.addNode();
	N33 = tree2.addNode();
	N321 = tree2.addNode();
		
	tree2.addEdge(Nroot, N1);
	tree2.addEdge(Nroot, N2);
	tree2.addEdge(Nroot, N3);
	tree2.addEdge(N2, N21);
	tree2.addEdge(N3, N31);
	tree2.addEdge(N3, N32);
	tree2.addEdge(N3, N33);
	tree2.addEdge(N33, N321);
	
	return tree2;

def MCMF(N1, N2, graph, viewLabel):
	
	listData = []; # (Edge, cost, capacity)
	tmpGraph = tlp.newSubGraph(graph, "tmpGraph");
	Ns = tmpGraph.addNode();
	viewLabel.setNodeValue(Ns, "s");
	Nt = tmpGraph.addNode();
	viewLabel.setNodeValue(Nt, "t");
	Nei = tmpGraph.addNode();
	viewLabel.setNodeValue(Nei, "ei");
	Nej = tmpGraph.addNode();
	viewLabel.setNodeValue(Nej, "ej");
		
	nk = 0;
	for k in graph.getOutNodes(N1):
		nk += 1;
	nl = 0;
	for l in graph.getOutNodes(N2):
		nl += 1;
	
	Eejt = tmpGraph.addEdge(Nej, Nt);
	listData.append((Eejt,0,nk));
	Eeiej = tmpGraph.addEdge(Nei, Nej);
	listData.append((Eeiej,0,max(nk, nl) - min (nk, nl)));
	
	listNk = [];
	listNl = [];
	for k in graph.getOutNodes(N1) :
		#print("forT1");
		Nk = tmpGraph.addNode();	
		viewLabel.setNodeValue(Nk, "k" + str(k));
		Esk = tmpGraph.addEdge(Ns, Nk);
		listData.append((Esk,0,1));
		
		Ekej = tmpGraph.addEdge(Nk, Nej);
		listData.append((Ekej, DT(k), 1));
		
		for l in graph.getOutNodes(N2) :
			Nl = tmpGraph.addNode();
			viewLabel.setNodeValue(Nl, "l" + str(l));
		
			Eeil = tmpGraph.addEdge(Nei, Nl);
			listData.append((Eeil, DT(l), 1));
		
			Elt = tmpGraph.addEdge(Nl, Nt);
			listData.append((Elt, 0, 1));
		
			Ekl = tmpGraph.addEdge(Nk, Nl);
			listData.append((Ekl, DTT(k, l), 1));
			
			
			
	return (tmpGraph, Ns, listData);

def DT(N) :
#N -> racine de l'arbre dont on veut la distance d'édition;
	try :
		graph.getOutNode(N,1);
	except Exception :
		return 0;
	else:
		return  DF(N) + COST_INSER_DEL;
			# cout de deletion/insertion = 1;

def DF(N) :
#N -> racine de l'arbre dont est issue la sous foret 
# dont on veut la distance d'édition;

	try :
		graph.getOutNode(N,1);
	except Exception :
		return 0;
	else :
		DF = 0;
		for i in graph.getOutNodes(N):
			DF += DT(i);
	return DF;

def DFF(N1, N2):
	listMin1 = [];
	listMin2 = [];
	
	for t in graph.getOutNodes(N2):
		listMin1.append(DFF(N1, t) - DF(t));
	listMin1.sort();
	lm1 = 0;
	try : 
		lm1 = listMin1[0];
	except IndexError :
		lm1 = 0;
	DFF1 = DF(N2) + lm1;
	
	for s in graph.getOutNodes(N1):
		listMin2.append(DFF(s,N2) - DF(s));
	listMin2.sort();
	
	lm2 = 0;
	try : 
		lm2 = listMin2[0];
	except IndexError :
		lm2 = 0;
	DFF2 = DF(N1) + lm2;
	
#	DFF3 = MCMF(N1, N2);
#	return min(DFF1, DFF2, DFF3);
	return min(DFF1, DFF2);
	

def DTT(N1, N2) :
	listMin1 = [];
	listMin2 = [];
	for t in graph.getOutNodes(N2) :
		listMin1.append(DTT(N1, t) - DT(t));
	listMin1.sort();
	lm1 = 0;
	try : 
		lm1 = listMin1[0];
	except IndexError :
		lm1 = 0;
	DTT1 = DT(N2) + lm1;
	
	for s in graph.getOutNodes(N1) :
		DT1s = DT(s);
		listMin2.append(DTT(s,N2) - DT(s))
	listMin2.sort();
	
	lm2 = 0;
	try : 
		lm2 = listMin2[0];
	except IndexError :
		lm2 = 0;
	DTT2 = DT(N1) + lm2;
	
	DTT3 = DFF(N1, N2) + COST_SUB;
	
	return min(DTT1, DTT2, DTT3);
	
def DTGeneral(T1, T2):
	listDTT = [[] for i in T1.getNodes()]
	id = 0;
	for i in T1.getNodes():
		for j in T2.getNodes():
			listDTT[id].append(DTT(i,j));
		id+= 1;
	return listDTT;

def initLayout(viewLayout) :
	dataSet = tlp.getDefaultPluginParameters("Tree Leaf", graph)
	dataSet["3D layout"] = False;
	graph.computeLayoutProperty("Tree Leaf", viewLayout, dataSet);
	viewLayout.scale(tlp.Coord(.5,.5,.5));
	
def main(graph) : 
	viewBorderColor =  graph.getColorProperty("viewBorderColor")
	viewBorderWidth =  graph.getDoubleProperty("viewBorderWidth")
	viewColor =  graph.getColorProperty("viewColor")
	viewFont =  graph.getStringProperty("viewFont")
	viewFontSize =  graph.getIntegerProperty("viewFontSize")
	viewLabel =  graph.getStringProperty("viewLabel")
	viewLabelColor =  graph.getColorProperty("viewLabelColor")
	viewLabelPosition =  graph.getIntegerProperty("viewLabelPosition")
	viewLayout =  graph.getLayoutProperty("viewLayout")
	viewMetaGraph =  graph.getGraphProperty("viewMetaGraph")
	viewRotation =  graph.getDoubleProperty("viewRotation")
	viewSelection =  graph.getBooleanProperty("viewSelection")
	viewShape =  graph.getIntegerProperty("viewShape")
	viewSize =  graph.getSizeProperty("viewSize")
	viewSrcAnchorShape =  graph.getIntegerProperty("viewSrcAnchorShape")
	viewSrcAnchorSize =  graph.getSizeProperty("viewSrcAnchorSize")
	viewTexture =  graph.getStringProperty("viewTexture")
	viewTgtAnchorShape =  graph.getIntegerProperty("viewTgtAnchorShape")
	viewTgtAnchorSize =  graph.getSizeProperty("viewTgtAnchorSize")
	global COST_SUB;
	COST_SUB = 5;
	global COST_INSER_DEL;
	COST_INSER_DEL = 1;
	graph.clear();
	tree1 = makeTreeA(graph, viewColor, viewLabel);
	print(tree1);

	tree2 = makeTreeB(graph, viewColor, viewLabel);
	print(tree2);
	
	
	DTTlist = DTGeneral(tree1, tree2);
	
	print(DTTlist);
	initLayout(viewLayout);
	return True;
